package main.java.algorithms;

import main.java.utils.SortTestHelper;

import java.util.Random;

/**
 * @author Wrb
 * @date 2019/5/27 18:29
 */
public class QuickSort3 implements Sort {
	@Override
	public void sort(int[] arr, int n) {
		sort(arr, 0, n - 1);
	}

	//递归进行快排
	private void sort(int[] arr, int l, int r) {

		//优化1 当数组小到一定程度，插入排序比归并排序快，此时调用插入排序
		if (r - l <= 20) {
			InsertionSort.sort(arr, l, r);
			return;
		}

		//partition
		//三路快速
		//优化2：随机选取基准
		SortTestHelper.swap(arr, l, new Random().nextInt(r - l + 1) + l);
		int v = arr[l];

		int lt = l;
		int gt = r + 1;
		int i = l + 1;
		while (i < gt) {
			if (arr[i] < v) {
				SortTestHelper.swap(arr, i, lt + 1);
				lt++;
				i++;
			} else if (arr[i] > v) {
				SortTestHelper.swap(arr, i, gt - 1);
				gt--;
			}else {
				i++;
			}
		}
		SortTestHelper.swap(arr, l, lt);

		sort(arr, l, lt - 1);
		sort(arr, gt, r);
	}

}
